1. Field
This disclosure relates to Huffman decoding.
2. Background Information
As is well-known, Huffman coding is a popular variable length statistical encoding scheme. As is also well-known, Huffman code generation relies on statistical probabilities for each individual symbol. See, for example, D. A. Huffman, xe2x80x9cA Method for the Reconstruction of Minimum-Redundancy Codesxe2x80x9d, Proceedings of the IRE (Institute of Electrical and Radio Engineers), Volume 40, No. 9, pages 1098-1101, 1952. A traditional table lookup based encoding scheme is widely used for Huffman encoding due, at least in part, to its efficiency and relative ease of implementation. However, table searching based decoding is typically inefficient in both software and hardware implementations. This is especially the case when the number of entries in a table is reasonably high, as is typical for practical applications.
Another approach employed for Huffman decoding is the creation of a Huffman tree, which employs a xe2x80x9ctree traversing technique.xe2x80x9d However, this decoding technique also has disadvantages. This particular technique is bit sequential, and introduces extra xe2x80x9coverheadxe2x80x9d both in terms of memory allocation and the execution of computations for the Huffman tree generation process and for the decoding process.